import java.util.*;

public class RankingAdjustment {

    public static boolean canFindValidRanking(int[] a) {
        int n = a.length;

        // 构建有向图的邻接表
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[n];  // 入度数组，用于拓扑排序

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // 根据数组 a 构建图
        for (int i = 0; i < n - 1; i++) {
            if (a[i] == 1) {
                graph.get(i).add(i + 1);  // i -> i + 1
                inDegree[i + 1]++;
            } else if (a[i] == -1) {
                graph.get(i + 1).add(i);  // i + 1 -> i
                inDegree[i]++;
            }
        }

        // 拓扑排序
        Queue<Integer> queue = new LinkedList<>();

        // 将入度为 0 的节点入队
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        int visitedCount = 0;  // 记录拓扑排序访问的节点数

        while (!queue.isEmpty()) {
            int node = queue.poll();
            visitedCount++;

            for (int neighbor : graph.get(node)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // 如果所有节点都被访问过，则说明没有环，返回 true，否则返回 false
        return visitedCount == n;
    }

    public static void main(String[] args) {
        // 测试用例
        int[] a1 = {1, -1, 0};  // 可行
        int[] a2 = {1, 1, -1};  // 不可行，有环
        int[] a3 = {0, 0, 0};   // 全部合理，肯定可行
        int[] a4 = {-1, 1, -1}; // 可行

        System.out.println(canFindValidRanking(a1));  // true
        System.out.println(canFindValidRanking(a2));  // false
        System.out.println(canFindValidRanking(a3));  // true
        System.out.println(canFindValidRanking(a4));  // true
    }
}
